package com.leetcode.No1104;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @program: leetcode
 * @description: 二叉树寻路
 * @author: wangzhihua
 * @date: 2021-07-30
 */
public class Solution01 {

	@Test
	public void getPowerOf2() {
		int ans = 1;
		System.out.print("{" + ans + ", ");
		while (ans < (1 << 21)) {
			ans <<= 1;
			System.out.print(ans + ", ");
		}
		System.out.println((ans<<1) + "}");
	}

	@Test
	public void test01() {
		System.out.println(pathInZigZagTree(16));
	}

	public List<Integer> pathInZigZagTree(int label) {
		int[] powerOf2 = new int[]{1, 2, 4, 8, 16, 32, 64, 128, 256, 512,
				1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072,
				262144, 524288, 1048576, 2097152, 4194304};
		int index = 0;
		while (powerOf2[index] < label && label >= powerOf2[index + 1]) {
			++index;
		}
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(label);
		while (--index >= 0) {
			label = powerOf2[index] + powerOf2[index + 1] - 1 - (label >> 1);
			list.add(label);
		}
		Collections.reverse(list);
		return list;
	}

}
